/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package sorts;

/**
 *
 * @author Matias
 */
public class quickSort extends sort{
    public static void sort(int data[], int n)
        // post: the values in data[0..n-1] are in ascending order
    {
        quickSortRecursive(data,0,n-1);
        for(int i=0 ; i< n ; i++)
            System.out.println(data[i]);
    }
        
    private static void quickSortRecursive(int data[],int left,int right)
        // pre: left <= right
        // post: data[left..right] in ascending order
    {
        int pivot; // the final location of the leftmost value
        if (left >= right) return;
        pivot = partition(data,left,right); /* 1 - place pivot */
        quickSortRecursive(data,left,pivot-1); /* 2 - sort small */
        quickSortRecursive(data,pivot+1,right);/* 3 - sort large */
        /* done! */
    }
    
    private static int partition(int data[], int left, int right)
// pre: left <= right
// post: data[left] placed in the correct (returned) location
    {
        while (true)
        {
            // move right "pointer" toward left
            while (left < right && data[left] < data[right]) right--;
                if (left < right) swap(data,left++,right);
                    else return left;
            // move left pointer toward right
            while (left < right && data[left] < data[right]) left++;
                if (left < right) swap(data,left,right--);
                    else return right;
        }
        
    }

    
}
